class Solution {
public:
    int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
        // dp[i][j][k] 表示：从前i个计划中挑选，总人数不超过j，总利润至少为k，一共有多少种选法
        const int MOD = 1e9 + 7; // 注意结果取模
        int len = group.size();
        vector<vector<int>> dp(n + 1, vector<int>(minProfit + 1));
        for(int j = 0; j <= n; j++)
        {
            dp[j][0] = 1; // 初始化
        }
        for(int i = 1; i <= len; ++i)
        {
            for(int j = n; j >= group[i - 1]; --j)
            {
                for(int k = minProfit; k >= 0; --k)
                {
                    dp[j][k] += dp[j - group[i - 1]][max(0, k - profit[i - 1])];
                    dp[j][k] %= MOD; // 注意结果取模
                }
            }
        }
        return dp[n][minProfit];
    }
};